package leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 无重复字符的最长子串
 * 给定一个字符串，找出不含有重复字符的最长子串的长度。
 *
 * 示例：
 *
 * 给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
 *
 * 给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
 *
 * 给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列  而不是子串。
 */
public class Code03 {
    public static void main(String[] args) {
        System.out.println(new Code03().lengthOfLongestSubstring2("asdasddd"));
    }

    /**
     * 第一版     没有考虑到优化的问题
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0){
            return 0;
        }
        char[] at=s.toCharArray();
        int start = 0;
        int end =1;
        int maxLength=1;
        int nowLength=1;
        HashMap<Character,Integer> map = new HashMap<>();
        map.put(at[0],0);
        while(end<at.length){
            Integer integer = map.get(at[end]);
            if (integer!=null){
                nowLength-=integer-start+1;
                start=integer+1;
                map.clear();
                for (int a=start;a<end;a++){
                    map.put(at[a],a);
                }
            }
            map.put(at[end],end);
            end++;
            nowLength++;
            maxLength = maxLength>nowLength?maxLength:nowLength;
        }
        return maxLength;
    }



    /**
     * 优化的方法就是优化之前的hashset数组。并不需要每次都算一下，只需要就是下标比现在大的就可以了
     * 动态规划
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring2(String s) {
        int[] map = new int[256];
        for (int a=0;a<map.length;a++){
            map[a]=-1;
        }
        char[] at = s.toCharArray();
        int start=0;
        int length = 0;
        for (int a=0;a<at.length;a++){
            if (map[at[a]]>=start){
                start= map[at[a]]+1;
            }
            length= Math.max(length,a-start+1);
            map[at[a]]=a;
        }
        return length;
    }
}
